package com.zzy.sort;

/*147. 对链表进行插入排序*/
public class LC147InsertionSortList {
    public static ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        //前驱节点
        ListNode top = new ListNode();
        top.next = head;
        //插入排序分左侧有序和右侧无序，开始时第一个节点就是有序的末尾
        ListNode lastSorted = head;
        //需要插入的节点
        ListNode cur = head.next;
        while (cur != null) {

            if (cur.val >= lastSorted.val) {
                //本次插入的比有序里最大的都大
                lastSorted = lastSorted.next;
            } else {
                //从头找位置
                ListNode node = top;
                while (node.next.val <= cur.val) {
                    node = node.next;
                }
                //插到当前node之后
                //!!!先把cur踢出来
                lastSorted.next = cur.next;
                cur.next = node.next;
                node.next = cur;
            }

            cur = lastSorted.next;
        }

        return top.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(-1);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(0);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode node = insertionSortList(node1);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}